#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll n,k;
		cin>>n>>k;
		ll q=pow(2,30);
		if(k<=30)
		{
			q=pow(2,k-1);
		}
		else k=31;
		int a[40]={0};
//		cout<<q<<endl;
		for(int i=k-1;i>=0;i--)
		{
			if(n>=q)
			{
				a[i]=1;
				n-=q;
			}
			q/=2;
		}
//		for(int i=0;i<k;i++) cout<<a[i]<<' ';
        ll ans=0;
        for(int i=k-1;i>=0;i--)
        {
        	ans=ans*2+a[i];
		}
		cout<<ans+1<<endl;
	}

	return 0;
}

